/*
 * GroebnerBasis.java
 *
 * Created on July 2, 2004, 7:17 PM
 */

package com.milowski.monos.binomial;

import java.util.*;
import java.io.*;
import java.util.logging.*;
import com.milowski.monos.monomial.*;

/**
 *
 * @author  R. Alexander Milowski
 */
public class GroebnerBasis {

   static class BasisData {
      int length = 0;
      FullBinomial [] data = null;
      public void extend(int length) {
         if (data==null) {
            data = new FullBinomial[length];
         } else {
             FullBinomial [] newbasis = new FullBinomial[data.length+length];
             System.arraycopy(data,0,newbasis,0, data.length);
             data = newbasis;
         }
      }
   }
   
   public interface Ordering {
      String getName();
      int compare(short [] values);
      int compare(int [] reorder,short [] values);
      int compare(short [] first, short [] second);
      int compare(int [] reorder,short [] first, short [] second);
   }
   
   public static class LexicographicOrdering implements Ordering {
      public String getName() { return "lex"; }
      public int compare(short [] values) {
         int firstNotZero=0;
         while (firstNotZero<values.length && values[firstNotZero]!=0) { 
            firstNotZero++; 
         } 
         return firstNotZero==values.length ? 0 : values[firstNotZero]>0 ? 1 : -1;
      }
      public int compare(int [] reorder,short [] values) {
         //if (reorder==null) {
         //   return compare(values);
         //}
         int firstNotZero=0;
         while (firstNotZero<values.length && values[reorder[firstNotZero]]!=0) { 
            firstNotZero++; 
         } 
         return firstNotZero==values.length ? 0 : values[reorder[firstNotZero]]>0 ? 1 : -1;
      }
      
      public int compare(short [] first, short [] second) {
         int firstNotEqual=0;
         while (firstNotEqual<first.length && first[firstNotEqual]==second[firstNotEqual]) { 
            firstNotEqual++; 
         } 
         return firstNotEqual==first.length ? 0 : (first[firstNotEqual]>second[firstNotEqual] ? 1 : -1);
         
      }
      public int compare(int [] reorder,short [] first, short [] second) {
         //if (reorder==null) {
         //   return compare(first,second);
         //}
         int firstNotEqual=0;
         while (firstNotEqual<first.length && first[reorder[firstNotEqual]]==second[reorder[firstNotEqual]]) { 
            firstNotEqual++; 
         } 
         return firstNotEqual==first.length ? 0 : (first[reorder[firstNotEqual]]>second[reorder[firstNotEqual]] ? 1 : -1);         
      }
   }
   
   public static Ordering LEXICOGRAPHIC = new LexicographicOrdering();
   
   public static class ReverseLexicographicOrdering implements Ordering {
      public String getName() { return "revlex"; }
      public int compare(short [] values) {
         int firstNotZero=values.length-1;
         while (firstNotZero>=0 && values[firstNotZero]!=0) { 
            firstNotZero--; 
         } 
         return firstNotZero<0 ? 0 : values[firstNotZero]<0 ? 1 : -1;
      }
      public int compare(int [] reorder,short [] values) {
         //if (reorder==null) {
         //   return compare(values);
         //}
         int firstNotZero=values.length-1;
         while (firstNotZero>=0 && values[reorder[firstNotZero]]!=0) { 
            firstNotZero--; 
         } 
         return firstNotZero<0 ? 0 : values[reorder[firstNotZero]]<0 ? 1 : -1;
      }
      public int compare(short [] first, short [] second) {
         int firstNotEqual=first.length-1;
         while (firstNotEqual>=0 && first[firstNotEqual]==second[firstNotEqual]) { 
            firstNotEqual--; 
         } 
         return firstNotEqual<0 ? 0 : (first[firstNotEqual]<second[firstNotEqual] ? 1 : -1);
         
      }
      public int compare(int [] reorder,short [] first, short [] second) {
         //if (reorder==null) {
         //   return compare(first,second);
         //}
         int firstNotEqual=first.length-1;
         while (firstNotEqual>=0 && first[reorder[firstNotEqual]]==second[reorder[firstNotEqual]]) { 
            firstNotEqual--; 
         } 
         return firstNotEqual==first.length ? 0 : (first[reorder[firstNotEqual]]<second[reorder[firstNotEqual]] ? 1 : -1);         
      }
   }
   
   public static Ordering REVERSE_LEXICOGRAPHIC = new ReverseLexicographicOrdering();
   
   public static class DegreeReverseLexicographicOrdering implements Ordering {
      public String getName() { return "degrevlex"; }
      public int compare(short [] values) {
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=values.length-1; i>=0; i--) {
            if (firstNotZero<0 && values[i]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0) {
               ftotal += values[i];
            } else {
               stotal += -values[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[firstNotZero]<0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] values) {
         //if (reorder==null) {
         //   return compare(values);
         //}
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=values.length-1; i>=0; i--) {
            if (firstNotZero<0 && values[reorder[i]]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0) {
               ftotal += values[i];
            } else {
               stotal += -values[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[reorder[firstNotZero]]<0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(short [] first, short [] second) {
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=first.length-1; i>=0; i--) {
            if (firstNotEqual<0 && first[i]!=second[i]) { 
               firstNotEqual = i;
            }
            ftotal += first[i];
            stotal += second[i];
         } 
         if (ftotal==stotal) {
            return firstNotEqual<0 ? 0 : (first[firstNotEqual]<second[firstNotEqual] ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] first, short [] second) {
         //if (reorder==null) {
         //   throw new IllegalArgumentException("reorder should not be null");
            //return compare(first,second);
         //}
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=first.length-1; i>=0; i--) {
            if (firstNotEqual<0 && first[reorder[i]]!=second[reorder[i]]) { 
               firstNotEqual = i;
            }
            ftotal += first[i];
            stotal += second[i];
         } 
         if (ftotal==stotal) {
            return firstNotEqual<0 ? 0 : (first[reorder[firstNotEqual]]<second[reorder[firstNotEqual]] ? 1 : -1);         
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
   }

   public static Ordering DEGREE_REVERSE_LEXICOGRAPHIC = new DegreeReverseLexicographicOrdering();
   
   public static class WeightedReverseLexicographicOrdering implements Ordering {
      public String getName() { return "wdegrevlex"; }
      int [] w;
      public WeightedReverseLexicographicOrdering(int [] weights) {
         w = weights;
      }

      public WeightedReverseLexicographicOrdering(short [] weights) {
         w = new int[weights.length];
         for (int i=0; i<weights.length; i++) {
            w[i] = weights[i];
         }
      }
      public int compare(short [] values) {
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=values.length-1; i>=0; i--) {
            if (firstNotZero<0 && values[i]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0) {
               ftotal += w[i]==1 ? values[i] : (w[i]==0 ? 0 : w[i]*values[i]);
            } else {
               stotal += w[i]==1 ? -values[i] : (w[i]==0 ? 0 : -w[i]*values[i]);
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[firstNotZero]<0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] values) {
         //if (reorder==null) {
         //   return compare(values);
         //}
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=values.length-1; i>=0; i--) {
            if (firstNotZero<0 && values[reorder[i]]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0) {
               ftotal += w[i]==1 ? values[i] : (w[i]==0 ? 0 : w[i]*values[i]);
            } else {
               stotal += w[i]==1 ? -values[i] : (w[i]==0 ? 0 : -w[i]*values[i]);
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[reorder[firstNotZero]]<0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(short [] first, short [] second) {
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=first.length-1; i>=0; i--) {
            if (firstNotEqual<0 && first[i]!=second[i]) { 
               firstNotEqual = i;
            }
            if (w[i]!=0) {
               ftotal += w[i]==1 ? first[i] : w[i]*first[i];
               stotal += w[i]==1 ? second[i] : w[i]*second[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotEqual<0 ? 0 : (first[firstNotEqual]<second[firstNotEqual] ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] first, short [] second) {
         //if (reorder==null) {
         //   return compare(first,second);
         //}
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=first.length-1; i>=0; i--) {
            if (firstNotEqual<0 && first[reorder[i]]!=second[reorder[i]]) { 
               firstNotEqual = i;
            }
            if (w[i]!=0) {
               ftotal += w[i]==1 ? first[i] : w[i]*first[i];
               stotal += w[i]==1 ? second[i] : w[i]*second[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotEqual<0 ? 0 : (first[reorder[firstNotEqual]]<second[reorder[firstNotEqual]] ? 1 : -1);         
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
   }

   public static class WeightedLexicographicOrdering implements Ordering {
      public String getName() { return "wlex"; }
      int [] w;
      public WeightedLexicographicOrdering(int [] weights) {
         w = weights;
      }

      public WeightedLexicographicOrdering(short [] weights) {
         w = new int[weights.length];
         for (int i=0; i<weights.length; i++) {
            w[i] = weights[i];
         }
      }
      public int compare(short [] values) {
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=0; i<values.length; i++) {
            if (firstNotZero<0 && values[i]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0 && w[i]!=0) {
               ftotal += w[i]==1 ? values[i] : w[i]*values[i];
            } else {
               stotal += w[i]==1 ? -values[i] : -w[i]*values[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[firstNotZero]>0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] values) {
         //if (reorder==null) {
         //   return compare(values);
         //}
         int ftotal = 0;
         int stotal = 0;
         int firstNotZero = -1;
         for (int i=0; i<values.length; i++) {
            if (firstNotZero<0 && values[reorder[i]]!=0) { 
               firstNotZero = i;
            }
            if (values[i]>=0 && w[i]!=0) {
               ftotal += w[i]==1 ? values[i] : w[i]*values[i];
            } else {
               stotal += w[i]==1 ? -values[i] : -w[i]*values[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotZero<0 ? 0 : (values[reorder[firstNotZero]]>0 ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(short [] first, short [] second) {
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=0; i<first.length; i++) {
            if (firstNotEqual<0 && (first[i]!=0 || second[i]!=0)) { 
               firstNotEqual = i;
            }
            if (w[i]!=0) {
               ftotal += w[i]==1 ? first[i] : w[i]*first[i];
               stotal += w[i]==1 ? second[i] : w[i]*second[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotEqual<0 ? 0 : (first[firstNotEqual]>second[firstNotEqual] ? 1 : -1);
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
      public int compare(int [] reorder,short [] first, short [] second) {
         //if (reorder==null) {
         //   return compare(first,second);
         //}
         int firstNotEqual = -1;
         int ftotal = 0;
         int stotal = 0;
         for (int i=0; i<first.length; i++) {
            if (firstNotEqual<0 && (first[i]!=0 || second[i]!=0)) { 
               firstNotEqual = i;
            }
            if (w[i]!=0) {
               ftotal += w[i]==1 ? first[i] : w[i]*first[i];
               stotal += w[i]==1 ? second[i] : w[i]*second[i];
            }
         } 
         if (ftotal==stotal) {
            return firstNotEqual==first.length ? 0 : (first[reorder[firstNotEqual]]>second[reorder[firstNotEqual]] ? 1 : -1);         
         } else {
            return ftotal>stotal ? 1 : -1;
         }
      }
   }
   
   BinomialIdeal basis;
   LexOrder order;
   Logger log;
   Ordering monomialOrdering;
   int reorder[];
   boolean autoreduce;
   
   /** Creates a new instance of GroebnerBasis */
   public GroebnerBasis(LexOrder order) {
      this.log = Logger.getLogger("com.milowski.monos.binomial");
      this.order = order;
      this.reorder = null;
      basis = new BinomialIdeal(order);
      monomialOrdering = DEGREE_REVERSE_LEXICOGRAPHIC;
      this.autoreduce = true;
      //monomialOrdering = REVERSE_LEXICOGRAPHIC;
      //monomialOrdering = LEXICOGRAPHIC;
   }
   
   public LexOrder getLexOrder() {
      return order;
   }
   
   public void setAutoReduce(boolean flag) {
      autoreduce = flag;
   }
   
   public void setMonomialOrdering(Ordering ordering) {
      monomialOrdering = ordering;
   }
   
   public void setLog(Logger log) {
      this.log = log;
   }
   
   public void setExponentReOrdering(int [] reorder) {
      if (reorder.length!=order.size()) {
         throw new IllegalArgumentException("The reordering is not of the same size as the exponent vectors.");
      }
      this.reorder = reorder;
   }
   
   public void computeToricIdeal(List matrixKernelBasis,short [] positiveRowVector) {
      int [] ivec = new int[positiveRowVector.length];
      for (int i=0; i<ivec.length; i++) {
         ivec[i] = positiveRowVector[i];
      }
      computeToricIdeal(matrixKernelBasis, ivec);
   }
   
    public void computeToricIdeal(List matrixKernelBasis,int [] positiveRowVector) {
      Ordering savedOrdering = monomialOrdering;
      int [] reorderSave = reorder;
      if (positiveRowVector.length!=order.size()) {
         throw new IllegalArgumentException("The row vector dimension is not the same as the lex order size: "+positiveRowVector.length+"!="+order.size());
      }
      // Check for a one vector
      boolean allOnes = true;
      for (int i=0; i<positiveRowVector.length; i++) {
         if (positiveRowVector[i]!=1) {
            allOnes = false;
         }
      if (positiveRowVector[i]<=0) {
            throw new IllegalArgumentException("The row vector contains a non-postive entry.");
         }
      }
      // Pick grevlex is the vector is all ones, otherwise weighted.
      Ordering w = allOnes ? DEGREE_REVERSE_LEXICOGRAPHIC : new WeightedReverseLexicographicOrdering(positiveRowVector);
      /*
      if (compact) {
         int bsize = matrixKernelBasis.size();
         // Compact the binomials
         for (int i=0; i<bsize; i++) {
            CompactBinomial b = ((Binomial)matrixKernelBasis.get(i)).toCompactBinomial();
            //if (monomialOrdering.compare(b.getValues())<0) {
            //   b.swap();
            //}
            matrixKernelBasis.set(i,b);
         }
         monomialOrdering = w;
         boolean isFineLog = log.isLoggable(Level.FINE);
         int len = order.size();
         reorder = new int[len];
         int reorderEnd = reorder.length-1;
         for (int i=0; i<reorder.length; i++) {
            reorder[i] = i;
         }
         boolean [] alreadySaturated = new boolean[len];
         for (int i=0; i<alreadySaturated.length; i++) {
            alreadySaturated[i] = false;
         }
         for (int var=0; var<len; var++) {
            if (alreadySaturated[var]) {
               if (isFineLog) {
                  log.fine("Variable "+var+" is already saturated and so there is nothing to do.");
               }
            } else {
               if (var!=0) {
                  matrixKernelBasis = basis;
                  basis = new ArrayList();
               }
               if (isFineLog) {
                  log.fine("Computing for variable "+var);
               }
               if (var!=0) {
                  reorder[var-1] = var-1;
               }
               reorder[reorderEnd] = var;
               reorder[var] = reorderEnd;
               if (isFineLog) {
                  log.fine("reorder: "+arrayToString(reorder));
               }
               computeCompactBasis(matrixKernelBasis);
               reorder[reorderEnd] = reorderEnd;
               reorder[var] = var;
            }
            int basisSize = basis.size();
            for (int i=0; i<basisSize; i++) {
               CompactBinomial b = (CompactBinomial)basis.get(i);
               short [] values = b.getValues();
               int partition = -1;
               boolean partitioned = true;
               if (isFineLog) {
                  log.fine("Checking for invertibles: "+arrayToString(values));
               }
               for (partition=-1; (partition+1)<values.length && values[partition+1]>=0; partition++);
               if (partition>0) {
                  if (isFineLog) {
                     log.fine("Partition: "+partition);
                  }
                  for (int j=partition+1; j<values.length; j++) {
                     if (values[j]>0) {
                        partitioned = false;
                     }
                  }
                  if (partitioned && partition>=var) {
                     log.fine("Invertible found:");
                     for (int j=var+1; j<len; j++) {
                        if (values[j]<0) {
                           if (isFineLog) {
                              log.fine("Variable "+j+" not needed.");
                           }
                           //alreadySaturated[j] = true;
                        }
                     }
                  }
               }
            }
         }
         matrixKernelBasis = basis;
         basis = new ArrayList();
         reorder = reorderSave;
         monomialOrdering = savedOrdering;
         computeCompactBasis(matrixKernelBasis);
      } else {
       */

         boolean isFineLog = log.isLoggable(Level.FINE);
         boolean isFinerLog = log.isLoggable(Level.FINER);
         BinomialTree initialTerms = new BinomialTree(order);
         
         BasisData abasis = convertToBasisData(matrixKernelBasis);
         
         if (isFineLog) {
            StringBuffer sb = new StringBuffer();
            for (int i=0; i<abasis.length; i++) {
               sb.append("   "+arrayToString(abasis.data[i].leading)+" - "+arrayToString(abasis.data[i].trailing));
               sb.append('\n');
            }
            log.fine("Kernel input: \n"+sb.toString());
         }
         
         monomialOrdering = w;
         int len = order.size();
         reorder = new int[len];
         int reorderEnd = reorder.length-1;
         short [] combined = new short[len];
         boolean [] alreadySaturated = new boolean[len];
         boolean [] processed = new boolean[len];
         for (int i=0; i<alreadySaturated.length; i++) {
            alreadySaturated[i] = false;
            processed[i] = false;
         }
         
         // Check for saturated variables
         for (int i=0; i<abasis.length; i++) {
            int positive = 0;
            int negative = 0;
            short [] lvalues = abasis.data[i].leading;
            short [] tvalues = abasis.data[i].trailing;
            // Determine the number of positive and negative components
            for (int var=0; var<len; var++) {
               combined[var] = (short)(lvalues[var]-tvalues[var]);
               if (!processed[var]) {
                  if (combined[var]>0) {
                     positive++;
                  } else if (combined[var]<0) {
                     negative++;
                  }
               }
            }
            if (positive<=negative) {
               for (int var=0; var<len; var++) {
                  if (!processed[var] && !alreadySaturated[var]) {
                     if (combined[var]>0) {
                        // Saturation needs to happen for this variable
                        processed[var] = true;
                     } else if (combined[var]<0) {
                        // The ideal is automatically saturated by the variables corresponding
                        // to the negative exponents.
                        processed[var] = true;
                        alreadySaturated[var] = true;
                        log.fine("Variable "+var+" is already saturated.");
                     }
                  }
               }
            } else {
               for (int var=0; var<len; var++) {
                  if (!processed[var] && !alreadySaturated[var]) {
                     if (combined[var]<0) {
                        // Saturation needs to happen for this variable
                        processed[var] = true;
                     } else if (combined[var]>0) {
                        // The ideal is automatically saturated by the variables corresponding
                        // to the positive exponents.
                        //alreadySaturated[var] = true;
                        if (isFineLog) {
                           log.fine("Variable "+var+" is already saturated.");
                        }
                     }
                  }
               }
            }
         }
         
         for (int i=0; i<reorder.length; i++) {
            reorder[i] = i;
         }
         /*
         int var = 0;
         int increment = 2;
         while (var<len) {
            if (alreadySaturated[var]) {
               if (isFineLog) {
                  log.fine("Variable "+var+" is already saturated and so there is nothing to do.");
               }
            } else {
               processed[var] = true;
               if (isFineLog) {
                  log.fine("Computing for variable "+var);
               }
               reorder[reorderEnd] = var;
               reorder[var] = reorderEnd;
               if (isFineLog) {
                  log.fine("reorder: "+arrayToString(reorder));
               }
               abasis = computeFullBasisInternal(initialTerms,abasis);
               reorder[reorderEnd] = reorderEnd;
               reorder[var] = var;
               for (int i=0; i<abasis.length; i++) {
                  FullBinomial b = abasis.data[i];
                  short [] lvalues = b.leading;
                  short [] tvalues = b.trailing;
                  if (lvalues[var]!=0 && tvalues[var]!=0) {
                     int min = lvalues[var]<tvalues[var] ? lvalues[var] : tvalues[var];
                     lvalues[var] -= min;
                     tvalues[var] -= min;
                  }
                  int partition = -1;
                  boolean partitioned = true;
                  if (isFineLog) {
                     log.info("Checking for invertibles: "+arrayToString(lvalues)+" - "+arrayToString(tvalues));
                  }
                  for (partition=-1; (partition+1)<lvalues.length && (lvalues[partition+1]-tvalues[partition+1])==0; partition++);
                  if (partition>0 && (lvalues[partition+1]-tvalues[partition+1])>0) {
                     partition++;
                     if (partition<var) {
                        continue;
                     }
                     if (isFineLog) {
                        log.info("Partition: "+partition);
                        for (int e=0; e<len; e++) {
                           combined[e] = (short)(lvalues[e]-tvalues[e]);
                        }
                        log.info("Combined: "+arrayToString(combined));
                     }
                     for (int j=partition+1; j<lvalues.length; j++) {
                        if ((lvalues[j]-tvalues[j])>0) {
                           partitioned = false;
                        }
                     }
                     if (partitioned && partition>=var) {
                        log.fine("Invertible found:");
                        for (int j=var+1; j<len; j++) {
                           if ((lvalues[j]-tvalues[j])<0) {
                              if (isFineLog) {
                                 log.info("Variable "+j+" not needed.");
                              }
                              alreadySaturated[j] = true;
                           }
                        }
                     }
                  }
               }
            }
            if (var==0) {
               var += len/2-1;
            } else if (increment==2) {
               var += increment;
               increment = 1;
            } else {
               var++;
               increment = 2;
            }
         }*/
         int varMax = len-1;
         for (int var=0; var<varMax; var++) {
            /*
            if (processed[var]) {
               continue;
            }*/
            if (alreadySaturated[var]) {
               if (isFineLog) {
                  log.fine("Variable "+var+" is already saturated and so there is nothing to do.");
               }
            } else {
               if (isFineLog) {
                  log.fine("Computing for variable "+var);
               }
               reorder[reorderEnd] = var;
               reorder[var] = reorderEnd;
               if (isFineLog) {
                  log.fine("reorder: "+arrayToString(reorder));
               }
               abasis = computeFullBasisInternal(true,initialTerms,abasis);
               reorder[reorderEnd] = reorderEnd;
               reorder[var] = var;
            }
            for (int i=0; i<alreadySaturated.length; i++) {
               processed[i] = false;
            }
            // Check for saturated variables
            //log.info("Checking for saturations...");
            for (int i=0; i<abasis.length; i++) {
               FullBinomial b = abasis.data[i];
               short [] lvalues = b.leading;
               short [] tvalues = b.trailing;
               if (!alreadySaturated[var]) {
                  if (lvalues[var]!=0 && tvalues[var]!=0) {
                     int min = lvalues[var]<tvalues[var] ? lvalues[var] : tvalues[var];
                     lvalues[var] -= min;
                     tvalues[var] -= min;
                  }
               }
               // TODO: remove
               int tsum = 0;
               int lsum = 0;
               for (int e=0; e<lvalues.length; e++) {
                  lsum += lvalues[e];
                  tsum += tvalues[e];
               }
               if (lsum==0 && tsum==0) {
                  throw new RuntimeException("Zero binomial returned!");
               }
               int partition = -1;
               boolean partitioned = true;
               if (isFinerLog) {
                  log.info("Checking for invertibles: "+arrayToString(lvalues)+" - "+arrayToString(tvalues));
               }
               for (partition=-1; (partition+1)<lvalues.length && (lvalues[partition+1]-tvalues[partition+1])==0; partition++);
               if (partition>0 && partition<(lvalues.length-1) && (lvalues[partition+1]-tvalues[partition+1])>0) {
                  partition++;
                  if (partition<var) {
                     continue;
                  }
                  if (isFinerLog) {
                     log.info("Partition: "+partition);
                     for (int e=0; e<len; e++) {
                        combined[e] = (short)(lvalues[e]-tvalues[e]);
                     }
                     log.info("Combined: "+arrayToString(combined));
                  }
                  for (int j=partition+1; j<lvalues.length; j++) {
                     if ((lvalues[j]-tvalues[j])>0) {
                        partitioned = false;
                     }
                  }
                  if (partitioned && partition>=var) {
                     log.fine("Invertible found:");
                     for (int j=var+1; j<len; j++) {
                        if ((lvalues[j]-tvalues[j])<0) {
                           if (isFineLog) {
                              log.info("Variable "+j+" not needed.");
                           }
                           alreadySaturated[j] = true;
                        }
                     }
                  }
               }
            }
         }
         reorder = reorderSave;
         monomialOrdering = savedOrdering;
         //com.milowski.monos.tools.bigrub.setLogLevel(Level.FINER);
         abasis = computeFullBasisInternal(true,initialTerms,abasis);
         // Fix-up: remove common divisors
         /*
         int basisSize = basis.size();
         for (int i=0; i<basisSize; i++) {
            Binomial b = (Binomial)basis.get(i);
            short [] lvalues = b.getLeadingTerm();
            short [] tvalues = b.getTrailingTerm();
            boolean changed = false;
            for (int var=0; var<len; var++) {
               if (lvalues[var]!=0 && tvalues[var]!=0) {
                  int min = lvalues[var]<tvalues[var] ? lvalues[var] : tvalues[var];
                  lvalues[var] -= min;
                  tvalues[var] -= min;
                  changed = true;
               }
            }
            if (changed && monomialOrdering.compare(tvalues,lvalues)==1) {
               b.swap();
            }
         }*/
      basis = new BinomialIdeal(order);
      for (int i=0; i<abasis.length; i++) {
         basis.add(abasis.data[i]);
      }
      //}
   }

   public void computeFullBasis(List starter) {
      computeFullBasis(new BinomialTree(order),starter);
   }
   
   BasisData convertToBasisData(List starter) {
      boolean isFineLog = log.isLoggable(Level.FINE);
      boolean isFinerLog = log.isLoggable(Level.FINER);
      BasisData abasis = new BasisData();
      abasis.extend(512<starter.size() ? starter.size()+128 : 512);
      
      if (reorder==null) {
         for (Iterator toCheck=starter.iterator(); toCheck.hasNext(); ) {
            FullBinomial b = (FullBinomial)toCheck.next();
            abasis.data[abasis.length++] = new FullBinomial(b);
            short [] lvalues = b.leading;
            short [] tvalues = b.trailing;
            if (monomialOrdering.compare(lvalues,tvalues)<0) {
               b.swap();
               if (isFineLog) {
                  log.fine("Swapped to "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
               }
            }
            if (isFinerLog) {
               log.finer("input = "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
            }
         }
      } else {
         for (Iterator toCheck=starter.iterator(); toCheck.hasNext(); ) {
            FullBinomial b = (FullBinomial)toCheck.next();
            abasis.data[abasis.length++] = new FullBinomial(b);
            short [] lvalues = b.leading;
            short [] tvalues = b.trailing;
            if (monomialOrdering.compare(reorder,lvalues,tvalues)<0) {
               b.swap();
               if (isFineLog) {
                  log.fine("Swapped to "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
               }
            }
            if (isFinerLog) {
               log.finer("input = "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
            }
         }
         
      }
      return abasis;
   }
   
   public void computeFullBasis(BinomialTree initialTerms, List starter) {
      BasisData abasis = convertToBasisData(starter);
      abasis = computeFullBasisInternal(false,initialTerms, abasis);
      basis = new BinomialIdeal(order);
      for (int i=0; i<abasis.length; i++) {
         basis.add(abasis.data[i]);
      }
      
   }
   
   BasisData computeFullBasisInternal(boolean toric,BinomialTree initialTerms, BasisData abasis) {
      boolean isFineLog = log.isLoggable(Level.FINE);
      boolean isFinerLog = log.isLoggable(Level.FINER);
      initialTerms.reset();
      for (int i=0; i<abasis.length; i++) {
         FullBinomial b = abasis.data[i];
         short [] lvalues = b.leading;
         short [] tvalues = b.trailing;
         if (reorder==null) {
            if (monomialOrdering.compare(lvalues,tvalues)<0) {
               b.swap();
               if (isFinerLog) {
                  log.fine("Swapped to "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
               }
            }
         } else {
            if (monomialOrdering.compare(reorder,lvalues,tvalues)<0) {
               b.swap();
               if (isFinerLog) {
                  log.fine("Swapped to "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
               }
            }
         }
         if (isFinerLog) {
            log.finer("input = "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
         }
         initialTerms.addBinomial(b.leading,b,true);
      }
      //BinomialTree initialTerms = new BinomialTree(order);
      if (isFineLog) {
         log.fine("Monomial order is "+monomialOrdering.getName());
      }
      //BinomialTree onlyBasisElements = new BinomialTree(order);
      // swap to reverse lex if needed
      FullBinomial first = abasis.data[0];
      System.arraycopy(abasis.data,1, abasis.data, 0,abasis.length-1);
      abasis.length--;

      BasisData adds = abasis;
      BasisData newAdds = new BasisData();
      newAdds.extend(512);
      abasis = new BasisData();
      abasis.extend(512);
      abasis.data[abasis.length++] = first;
      
      if (isFinerLog) {
         log.finer("adding "+arrayToString(first.getLeadingTerm())+" - "+arrayToString(first.getTrailingTerm()));
      }
      //basis.add(first);
      //onlyBasisElements.addBinomial(first,true);
      short [] lcm = new short[order.size()]; 
      short [][] rterm = new short[2][];
      rterm[0] = new short[order.size()];
      rterm[1] = new short[order.size()];
      int firstLex = 0;
      int secondLex = 0;
      
      BinomialTree.BinomialDivisorIterator divisors = initialTerms.binomialDivisors(null);
      do {
         int added = 0;
//         if (isFineLog) {
//            log.fine("Auto-reducing the basis, size="+abasis.length);
//         }
//         autoReduce(toric,abasis,initialTerms);
         if (isFineLog) {
            log.fine("Status: #binomials="+adds.length+", basis size="+abasis.length);
         }
         
         if (autoreduce) {
            if (isFineLog) {
               log.fine("Auto-reducing the adds...");
            }
            autoReduce(toric,adds,initialTerms);
         }
            
         if (isFineLog) {
            log.fine("Status: #binomials="+adds.length+", basis size="+abasis.length);
         }
         
         //List newAdds = new ArrayList();
         newAdds.length = 0;
         long start = System.currentTimeMillis();
         for (int addIndex=0; addIndex<adds.length; addIndex++) {
            
            if (autoreduce && added>100) {
               if (isFineLog) {
                  log.fine("Auto-reducing the basis, size="+abasis.length);
               }
               autoReduce(toric,abasis,initialTerms);
               added = 0;
            }
            if (autoreduce && newAdds.length!=0 && newAdds.length%100==0) {
               if (isFineLog) {
                  log.fine("Auto-reducing the newAdds, size="+newAdds.length);
               }
               autoReduce(toric,newAdds,initialTerms);
            }
//            if (autoreduce && added>100) {
//               if (isFineLog) {
//                  log.fine("Auto-reducing the basis, size="+abasis.length);
//               }
//               autoReduce(abasis,initialTerms);
//
//               if (isFineLog) {
//                  log.fine("Merging adds, at="+addIndex+" adds="+adds.length+", new="+newAdds.length);
//               }
//               System.arraycopy(adds.data, addIndex, adds.data, 0, adds.length-addIndex);
//               adds.length -= addIndex;
//               //adds = adds.subList(addIndex, adds.size());
//               
//               // Merge the new adds and break to auto-reduce the adds
//               if (newAdds.length>0) {
//                  int neededLength = newAdds.length+adds.length;
//                  if (neededLength>=adds.length) {
//                     adds.extend(newAdds.length>128 ? newAdds.length : 128);
//                  }
//                  System.arraycopy(adds.data, adds.length-1,newAdds.data, 0, newAdds.length);
//               }
//               newAdds.length = 0;
//               //adds.addAll(newAdds);
//               //newAdds = adds;
//               added = 0;
//               long end = System.currentTimeMillis();
//               log.fine("Elapsed="+(end-start));
//               start = System.currentTimeMillis();
//               break;
//            }
            
            FullBinomial g = adds.data[addIndex];

            //int size = basis.size();

            if (isFinerLog) {
               log.finer(abasis.length+" Processing "+arrayToString(g.getLeadingTerm())+" - "+arrayToString(g.getTrailingTerm()));
            }

            if (isFineLog && addIndex%50==0) {
               long end = System.currentTimeMillis();
               log.fine("Status: at "+addIndex+", #binomials="+(adds.length-addIndex)+" basis size="+abasis.length+", elapsed="+(end-start));
               start = System.currentTimeMillis();
            }
            short [] g_lvalues = g.leading;
            short [] g_tvalues = g.trailing;
            boolean duplicate = false;
            
            for (int i=0; i<abasis.length; i++) {
               // Get binomials
               FullBinomial f = abasis.data[i];

               //log.fine("S-pair: ("+addIndex+","+i+")");
               /*
               if (isFineLog && i!=0 && i%500==0) {
                  long end = System.currentTimeMillis();
                  log.fine("S-pair: ("+addNumber+","+i+")");
               }*/
               // Calculate S-pair
               short [] f_lvalues = f.leading;
               short [] f_tvalues = f.trailing;
               
               boolean conflict = false;
               int leading = 0;
               int trailing = 1;
               int lastNonZero = -1;
               
               for (int e=0; e<f_lvalues.length; e++) {
                  if (f_lvalues[e]!=0 && g_lvalues[e]==0) {
                     // Assign value
                     rterm[leading][e] = (short)(f_tvalues[e]);
                     rterm[trailing][e] = (short)(f_lvalues[e]-g_lvalues[e]+g_tvalues[e]);
                     lcm[e] = f_lvalues[e];
                  } else if (f_lvalues[e]==0 && g_lvalues[e]!=0) {
                     // Assign value
                     rterm[leading][e] = (short)(g_lvalues[e]-f_lvalues[e]+f_tvalues[e]);
                     rterm[trailing][e] = (short)(g_tvalues[e]);
                     lcm[e] = g_lvalues[e];
                  } else if (f_lvalues[e]>g_lvalues[e]) {
                     conflict = true;
                     // Assign value
                     rterm[leading][e] = (short)(f_tvalues[e]);
                     rterm[trailing][e] = (short)(f_lvalues[e]-g_lvalues[e]+g_tvalues[e]);
                     lcm[e] = f_lvalues[e];
                  } else {
                     conflict = true;
                     // Assign value
                     rterm[leading][e] = (short)(g_lvalues[e]-f_lvalues[e]+f_tvalues[e]);
                     rterm[trailing][e] = (short)(g_tvalues[e]);
                     lcm[e] = g_lvalues[e];
                  }
                  if (toric) {
                     int value = rterm[leading][e]-rterm[trailing][e];
                     if (value<0) {
                        rterm[leading][e] = 0;
                        rterm[trailing][e] = (short)-value;
                     } else if (value>0) {
                        rterm[leading][e] = (short)value;
                        rterm[trailing][e] = 0;
                     } else {
                        rterm[leading][e] = 0;
                        rterm[trailing][e] = 0;
                     }
                  }
                  
                  if (rterm[leading][e]!=rterm[trailing][e]) {
                     lastNonZero = e;
                  }
               }
               
               // LCM is LT multiplied together
               if (!conflict) {
                  continue;
               }

               // TODO: this doesn't work for the Criterion
               /*
               if (onlyBasisElements.divides(lcm)) {
                  continue;
               }*/
               
               /*
            for (int e=0; e<lcm.length; e++) {
                  
                  // Assign value
                  rterm[leading][e] = (short)(lcm[e]-f_lvalues[e]+f_tvalues[e]);
                  rterm[trailing][e] = (short)(lcm[e]-g_lvalues[e]+g_tvalues[e]);
                  
                  if (rterm[leading][e]!=rterm[trailing][e]) {
                     lastNonZero = e;
                  }
                  
               }*/
               if (lastNonZero<0) {
                  // We've computed a S-pair with the same vector for f & g
                  // That means the add is a result of the S-pair of previous items
                  // in the initial list.  As a result, skip adding this element.
                  duplicate = true;
                  break;
               } else if (reorder==null) {
                  if (monomialOrdering.compare(rterm[trailing],rterm[leading])==1) {
                     leading = 1;
                     trailing = 0;
                  }
               } else {
                  if (monomialOrdering.compare(reorder,rterm[trailing],rterm[leading])==1) {
                     leading = 1;
                     trailing = 0;
                  }
               }

               // Divide S-pair by old basis
               // TODO: need "first divisor" method on monomial tree to minimize waste
               boolean divided;
               boolean divideNonZero;
               /*
               log.info("binomial tree contains: ");
               Iterator elements = initialTerms.iterator();
               while (elements.hasNext()) {
                  Binomial b = (Binomial)elements.next();
                  log.info("   "+arrayToString(b.getValues()));
               }
                */
               if (isFinerLog) {
                  log.finer("rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
               }
               do {
                  //log.info("Dividing...");
                  if (isFinerLog) {
                     log.finer("Dividing leading term...");
                  }
                  divided = false;
                  divideNonZero = true;
                  divisors.setDivided(rterm[leading]);
                  //Iterator divisors = initialTerms.binomialDivisors(rterm[leading]);
                  FullBinomial divisor = null;
                  //if (divisors.hasNext()) {
                     Object o = divisors.next();
                     if (o instanceof List) {
                        divisor = (FullBinomial)((List)o).get(0);
                     } else {
                        divisor = (FullBinomial)o;
                     }
                  //}
                  if (divisor!=null) {
                     short [] ldvalues = divisor.leading;
                     short [] tdvalues = divisor.trailing;
//                     boolean nonZero = false;
//                     for (int e=0; e<ldvalues.length; e++) {
//                        if ((ldvalues[e]-tdvalues[e])!=0) {
//                           nonZero = true;
//                        }
//                     }
//                     if (!nonZero) {
//                        log.severe("zero divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
//                     }
                     if (isFinerLog) {
                        log.finer("divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
                     }
                     divided = true;
                     divideNonZero = false;
                     int lastVar = -1;
                     // Do division calculation
                     for (int e=0; e<rterm[leading].length; e++) {
                        //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                        rterm[leading][e] = (short)(rterm[leading][e] - ldvalues[e] + tdvalues[e]);
                        if (toric) {
                           int value = rterm[leading][e]-rterm[trailing][e];
                           if (value<0) {
                              rterm[leading][e] = 0;
                              rterm[trailing][e] = (short)-value;
                           } else if (value>0) {
                              rterm[leading][e] = (short)value;
                              rterm[trailing][e] = 0;
                           } else {
                              rterm[leading][e] = 0;
                              rterm[trailing][e] = 0;
                           }
                        }
                        if (rterm[leading][e]!=rterm[trailing][e]) {
                           lastVar = e;
                           divideNonZero = true;
                        }
                     }
                     // Swap order if necessary in revlex
                     if (divideNonZero && lastVar>=0) {
                        if (reorder==null) {
                           if (monomialOrdering.compare(rterm[trailing],rterm[leading])==1) {
                              int temp = trailing;
                              trailing = leading;
                              leading = temp;
                           }
                        } else {
                           if (monomialOrdering.compare(reorder,rterm[trailing],rterm[leading])==1) {
                              int temp = trailing;
                              trailing = leading;
                              leading = temp;
                           }
                        }
                     }
                     if (isFinerLog) {
                        log.finer("rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                     }
                  }
               } while (divided && divideNonZero);
               //log.info("Finished dividing...");
               
               if (divideNonZero) {
                  
                  if (isFinerLog) {
                     log.finer("Remainder, dividing trailing monomial.");
                  }
                  
                  FullBinomial divisor = null;
                  boolean doAdd = true;
                  do {
                     divisors.setDivided(rterm[trailing]);
                     //Iterator divisors = initialTerms.binomialDivisors(rterm[trailing]);
                     //if (divisors.hasNext()) {
                     Object o = divisors.next();
                     if (o instanceof List) {
                        divisor = (FullBinomial)((List)o).get(0);
                     } else {
                        divisor = (FullBinomial)o;
                     }
                     if (divisor!=null) {
                        short [] ldvalues = divisor.leading;
                        short [] tdvalues = divisor.trailing;
//                        boolean nonZero = false;
//                        for (int e=0; e<ldvalues.length; e++) {
//                           if ((ldvalues[e]-tdvalues[e])!=0) {
//                              nonZero = true;
//                           }
//                        }
//                        if (!nonZero) {
//                           log.severe("zero divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
//                        }
                        if (isFinerLog) {
                           log.finer("divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
                        }
                        boolean allZero = true;
                        for (int e=0; e<rterm[trailing].length; e++) {
                           //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" =? rterm["+trailing+"]["+e+"] = "+rterm[trailing][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                           rterm[trailing][e] = (short)(rterm[trailing][e] - ldvalues[e] + tdvalues[e]);
                           if (toric) {
                              int value = rterm[leading][e]-rterm[trailing][e];
                              if (value<0) {
                                 rterm[leading][e] = 0;
                                 rterm[trailing][e] = (short)-value;
                                 allZero = false;
                              } else if (value>0) {
                                 rterm[leading][e] = (short)value;
                                 rterm[trailing][e] = 0;
                                 allZero = false;
                              } else {
                                 rterm[leading][e] = 0;
                                 rterm[trailing][e] = 0;
                              }
                           }
                           if (allZero) {
                              int diff = rterm[leading][e] - rterm[trailing][e];
                              if (diff!=0) {
                                 allZero = false;
                              }
                           }
                        }
                        if (isFinerLog) {
                           log.finer("Divide result, rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                        }
                        if (allZero) {
                           if (isFinerLog) {
                              log.finer("Zero binomial, rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                           }
                           divisor = null;
                           doAdd = false;
                        } else {
                           if (reorder==null) {
                              if (monomialOrdering.compare(rterm[trailing],rterm[leading])==1) {
                                 //throw new RuntimeException("Woah!");
                                 int temp = trailing;
                                 trailing = leading;
                                 leading = temp;
                              }
                           } else {
                              if (monomialOrdering.compare(reorder,rterm[trailing],rterm[leading])==1) {
                                 //throw new RuntimeException("Woah!");
                                 int temp = trailing;
                                 trailing = leading;
                                 leading = temp;
                              }
                           }
                           if (isFinerLog) {
                              log.finer("rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                           }
                        }
                     }
                     //} else {
                     //   divisor = null;
                     //}
                  } while (divisor!=null);

                  if (doAdd) {
                     if (isFinerLog) {
                        log.finer("Adding S-pair reduced: "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                     }
                     FullBinomial b = new FullBinomial(rterm[leading],rterm[trailing]);
                     if (newAdds.length==newAdds.data.length) {
                        newAdds.extend(128);
                     }
                     newAdds.data[newAdds.length++] = b;
                     initialTerms.addBinomial(b.leading, b,true);
                  }
               } else {
                  if (isFinerLog) {
                     log.finer("Reduces to zero, not added.");
                  }
               }
            }
            if (!duplicate) {
               if (isFinerLog) {
                  log.finer("adding basis element "+arrayToString(g.getLeadingTerm())+" - "+arrayToString(g.getTrailingTerm()));
               }
               if (abasis.length==abasis.data.length) {
                  abasis.extend(128);
               }
               abasis.data[abasis.length++] = g;
               //basis.add(g);
               //onlyBasisElements.addBinomial(g,true);
               added++;
            }
         }
         BasisData atemp = adds;
         adds = newAdds;
         newAdds = atemp;
         newAdds.length = 0;
      } while(adds.length!=0);

      if (autoreduce) {
         if (isFineLog) {
            log.fine("Final auto-reduce of the basis, size="+abasis.length);
         }
         autoReduce(toric,abasis,initialTerms);
      }
            
      // Reduce the basis
      if (isFinerLog) {
         log.fine("Basis size="+abasis.length);
      }
      if (isFinerLog) {
         StringBuffer sb = new StringBuffer();
         for (int i=0; i<abasis.length; i++) {
            Binomial b = abasis.data[i];
            sb.append(arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
            sb.append('\n');
         }
         log.fine("Input to reduce:\n"+sb.toString());
      }
      reduce(abasis,initialTerms);
      if (isFinerLog) {
         StringBuffer sb = new StringBuffer();
         for (int i=0; i<abasis.length; i++) {
            Binomial b = abasis.data[i];
            sb.append(arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
            sb.append('\n');
         }
         log.fine("Output from reduce:\n"+sb.toString());
      }
      if (isFineLog) {
         log.fine("Finished, size="+abasis.length);
      }
      return abasis;
   }
   
   private void autoReduce(boolean toric,BasisData abasis,BinomialTree initialTerms) {
      //com.milowski.monos.tools.bigrub.setLogLevel(Level.FINER);
      boolean isFineLog = log.isLoggable(Level.FINE);
      boolean isFinerLog = log.isLoggable(Level.FINER);
      short [][]rterm = new short[2][];
      short [] origLeading = new short[initialTerms.getLexOrder().size()];
      int reduced = 0;
      int removed = 0;
      BinomialTree.BinomialDivisorIterator divisors = initialTerms.binomialDivisors(null);
      
      if (isFineLog) {
         log.fine("Auto-reducing.");
      }
      for (int i=0; i<abasis.length; i++) {
         //log.info("Checking index "+i);
         FullBinomial b = abasis.data[i];
         int leading = 0;
         int trailing = 1;
         rterm[leading] = b.leading;
         rterm[trailing] = b.trailing;
         System.arraycopy(rterm[leading],0,origLeading,0,origLeading.length);
         
         if (isFinerLog) {
            log.finer("Checking binomial "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
         }
         boolean divided;
         boolean divideNonZero;
         boolean changed = false;
         do {
            //log.info("Dividing...");
            if (isFinerLog) {
               log.finer("Dividing leading term...");
            }
            divided = false;
            divideNonZero = true;
            divisors.setDivided(rterm[leading]);
            //Iterator divisors = initialTerms.binomialDivisors(rterm[leading]);
            FullBinomial divisor = null;
            while (divisors.hasNext() && divisor==null) {
               Object o = divisors.next();
               if (o==b) {
                  continue;
               }
               if (o instanceof List) {
                  List l = (List)o;
                  for (int t=0; t<l.size() && divisor==null; t++) {
                     divisor = (FullBinomial)l.get(t);
                     if (divisor==b) {
                        divisor = null;
                     }
                  }
               } else {
                  divisor = (FullBinomial)o;
               }
            }
            if (divisor!=null) {
               changed = true;
               short [] ldvalues = divisor.leading;
               short [] tdvalues = divisor.trailing;
               if (isFinerLog) {
                  log.finer("divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
               }
               divided = true;
               divideNonZero = false;
               int lastVar = -1;
               // Do division calculation
               for (int e=0; e<rterm[leading].length; e++) {
                  //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                  rterm[leading][e] = (short)(rterm[leading][e] - ldvalues[e] + tdvalues[e]);
                  if (toric) {
                     int value = rterm[leading][e]-rterm[trailing][e];
                     if (value<0) {
                        rterm[leading][e] = 0;
                        rterm[trailing][e] = (short)-value;
                     } else if (value>0) {
                        rterm[leading][e] = (short)value;
                        rterm[trailing][e] = 0;
                     } else {
                        rterm[leading][e] = 0;
                        rterm[trailing][e] = 0;
                     }
                  }
                  if (rterm[leading][e]!=rterm[trailing][e]) {
                     lastVar = e;
                     divideNonZero = true;
                  }
               }
               // Swap order if necessary in revlex
               if (divideNonZero && lastVar>=0) {
                  if (reorder==null) {
                     if (monomialOrdering.compare(rterm[trailing],rterm[leading])==1) {
                        int temp = trailing;
                        trailing = leading;
                        leading = temp;
                     }
                  } else {
                     if (monomialOrdering.compare(reorder,rterm[trailing],rterm[leading])==1) {
                        int temp = trailing;
                        trailing = leading;
                        leading = temp;
                     }
                  }
               }
               if (isFinerLog) {
                  log.finer("rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
               }
            }
         } while (divided && divideNonZero);
               
         if (divideNonZero) {

            if (isFinerLog) {
               log.finer("Remainder, dividing trailing monomial.");
            }

            FullBinomial divisor = null;
            do {
               if (isFinerLog) {
                  log.finer("Getting divisor list...");
               }
               divisor = null;
               divisors.setDivided(rterm[trailing]);
               //Iterator divisors = initialTerms.binomialDivisors(rterm[trailing]);
               while (divisors.hasNext() && divisor==null) {
                  Object o = divisors.next();
                  if (o==b) {
                     continue;
                  }
                  if (isFinerLog) {
                     log.finer("Searching divisor list...");
                  }
                  if (o instanceof List) {
                     List l = (List)o;
                     for (int t=0; t<l.size() && divisor==null; t++) {
                        divisor = (FullBinomial)l.get(t);
                        if (divisor==b) {
                           divisor = null;
                        }
                     }
                  } else {
                     divisor = (FullBinomial)o;
                  }
                  if (divisor!=null) {
                     short [] ldvalues = divisor.leading;
                     short [] tdvalues = divisor.trailing;
                     changed = true;
                     if (isFinerLog) {
                        log.finer("divisor = "+arrayToString(ldvalues)+" - "+arrayToString(tdvalues));
                     }
                     boolean allZero = true;
                     for (int e=0; e<rterm[trailing].length; e++) {
                        //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                        rterm[trailing][e] = (short)(rterm[trailing][e] - ldvalues[e] + tdvalues[e]);
                        if (toric) {
                           int value = rterm[leading][e]-rterm[trailing][e];
                           if (value<0) {
                              rterm[leading][e] = 0;
                              rterm[trailing][e] = (short)-value;
                              allZero = false;
                           } else if (value>0) {
                              rterm[leading][e] = (short)value;
                              rterm[trailing][e] = 0;
                              allZero = false;
                           } else {
                              rterm[leading][e] = 0;
                              rterm[trailing][e] = 0;
                           }
                        }
                        if (allZero) {
                           int diff = rterm[leading][e] - rterm[trailing][e];
                           if (diff!=0) {
                              allZero = false;
                           }
                        }
                     }
                     if (allZero) {
                        divisor = null;
                        changed = false;
                        if (isFinerLog) {
                           log.finer("Basis element divided, removing.");
                        }
                        removed++;
                        if (!initialTerms.removeBinomial(origLeading,b, true)) {
                           throw new RuntimeException("Algorithm failure: Binomial was not found in initial ideal.  Leading term was "+arrayToString(origLeading));
                        }
                        // TODO: there should be a better way
                        System.arraycopy(abasis.data, i+1, abasis.data,i, abasis.length-i-1);
                        i--;
                        abasis.length--;
                     } else {
                        if (reorder==null) {
                           if (monomialOrdering.compare(rterm[trailing],rterm[leading])==1) {
                              int temp = trailing;
                              trailing = leading;
                              leading = temp;
                           }
                        } else {
                           if (monomialOrdering.compare(reorder,rterm[trailing],rterm[leading])==1) {
                              int temp = trailing;
                              trailing = leading;
                              leading = temp;
                           }

                        }
                        if (isFinerLog) {
                           log.finer("rterm = "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
                        }
                     }
                  }
               }
            } while (divisor!=null);
            if (changed) {
               if (isFinerLog) {
                  log.finer("Basis element reduced, replacing with "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
               }
               reduced++;
               initialTerms.removeBinomial(origLeading,b, true);
               if (leading!=0) {
                  b.swap();
               }
               initialTerms.addBinomial(b.leading,b,true);
            }
         } else {
            if (isFinerLog) {
               log.finer("Basis element divided, removing.");
            }
            removed++;
            if (!initialTerms.removeBinomial(origLeading,b, true)) {
               throw new RuntimeException("Algorithm failure: Binomial was not found in initial ideal.  Leading term was "+arrayToString(origLeading));
            }
            // TODO: there should be a better way
            System.arraycopy(abasis.data, i+1, abasis.data,i, abasis.length-i-1);
            i--;
            abasis.length--;
         }
         if (isFinerLog) {
            log.finer("Resulting binomial "+arrayToString(rterm[leading])+" - "+arrayToString(rterm[trailing]));
         }

      }
      if (isFineLog) {
         log.fine("Auto-reduce finished: reduced="+reduced+", removed="+removed);
      }
      //com.milowski.monos.tools.bigrub.setLogLevel(Level.FINE);
   }
   
   private void compactSwap(short [] values) {
      for (int i=0; i<values.length; i++) {
         values[i] = (short)-values[i];
      }
   }
   
   /*
   public void computeCompactBasis(List starter) {
      boolean isFineLog = log.isLoggable(Level.FINE);
      boolean isFinerLog = log.isLoggable(Level.FINER);
      BinomialTree initialTerms = new BinomialTree(order);
      //BinomialTree onlyBasisElements = new BinomialTree(order);
      // swap to reverse lex if needed
      for (Iterator toCheck=starter.iterator(); toCheck.hasNext(); ) {
         CompactBinomial b = (CompactBinomial)toCheck.next();
         short [] values = b.getValues();
         if (monomialOrdering.compare(reorder,values)<0) {
            b.swap();
         }
         if (isFinerLog) {
            log.finer("input = "+arrayToString(b.getLeadingTerm())+" - "+arrayToString(b.getTrailingTerm()));
         }
         initialTerms.addBinomial(b,true);
      }
      List adds = starter;
      basis.clear();
      Binomial first = (Binomial)adds.remove(0);
      if (isFinerLog) {
         log.finer("adding "+arrayToString(first.getLeadingTerm())+" - "+arrayToString(first.getTrailingTerm()));
      }
      basis.add(first);
      //onlyBasisElements.addBinomial(first,true);
      short [] lcm = new short[order.size()]; 
      short [] rterm = new short[order.size()];
      int firstLex = 0;
      int secondLex = 0;
      int added = 0;
      do {
         if (isFineLog) {
            log.fine("Status: #binomials="+adds.size()+", basis size="+basis.size());
         }
         
         Iterator toAdd = adds.iterator();
         int addNumber = adds.size();

         List newAdds = new ArrayList();
         long start = System.currentTimeMillis();
         while (toAdd.hasNext()) {
            
            CompactBinomial g = (CompactBinomial)toAdd.next();
            addNumber--;

            
            int size = basis.size();

            if (isFinerLog) {
               log.finer(size+" Processing "+arrayToString(g.getValues()));
            }

            if (isFineLog && addNumber%100==0) {
               long end = System.currentTimeMillis();
               log.fine("Status: #binomials="+addNumber+", basis size="+basis.size()+", elapsed="+(end-start));
               start = System.currentTimeMillis();
            }
            short [] g_values = g.getValues();
            boolean duplicate = false;
            
            for (int i=0; i<size; i++) {
               // Get binomials
               CompactBinomial f = (CompactBinomial)basis.get(i);

               // Calculate S-pair
               short [] f_values = f.getValues();
               
               boolean conflict = false;
               int lastNonZero = -1;
               
               for (int e=0; e<f_values.length; e++) {
                  if (f_values[e]>=0 && g_values[e]>=0) {
                     if (f_values[e]!=0 && g_values[e]!=0) {
                        conflict = true;
                     }
                     lcm[e] = f_values[e]>g_values[e] ? f_values[e] : g_values[e];
                  } else {
                     lcm[e] = 0;
                  }
                  
                  int s_f = lcm[e] - f_values[e];
                  int s_g = lcm[e] - g_values[e];
                  if (s_f>=0 && s_g>0) {
                     if (s_f>s_g) {
                        s_f -= s_g;
                        s_g = 0;
                     } else {
                        s_g -= s_f;
                        s_f = 0;
                     }
                  }
                  rterm[e] = (short)(s_g-s_f);
                  
                  if (rterm[e]!=0) {
                     lastNonZero = e;
                  }
               }
               
               // LCM is LT multiplied together
               if (!conflict) {
                  continue;
               }
               
               boolean leadingIsFirst = true;

               if (lastNonZero<0) {
                  // We've computed a S-pair with the same vector for f & g
                  // That means the add is a result of the S-pair of previous items
                  // in the initial list.  As a result, skip adding this element.
                  duplicate = true;
                  break;
               } else {
                  if (monomialOrdering.compare(reorder,rterm)<0) {
                     leadingIsFirst = false;
                  }
               }

               // Divide S-pair by old basis
               // TODO: need "first divisor" method on monomial tree to minimize waste
               boolean divided;
               boolean divideNonZero;
               if (isFinerLog) {
                  log.finer("rterm = "+arrayToString(rterm)+", leadingIsFirst="+leadingIsFirst);
               }
               do {
                  //log.info("Dividing...");
                  if (isFineLog) {
                     log.finer("Dividing leading term...");
                  }
                  divided = false;
                  divideNonZero = true;
                  Iterator divisors = initialTerms.compactBinomialDivisors(rterm,leadingIsFirst);
                  CompactBinomial divisor = null;
                  if (divisors.hasNext()) {
                     Object o = divisors.next();
                     if (o instanceof List) {
                        divisor = (CompactBinomial)((List)o).get(0);
                     } else {
                        divisor = (CompactBinomial)o;
                     }
                  }
                  if (divisor!=null) {
                     short [] dvalues = divisor.getValues();
                     if (isFinerLog) {
                        log.finer("divisor = "+arrayToString(dvalues));
                     }
                     divided = true;
                     divideNonZero = false;
                     int lastVar = -1;
                     // Do division calculation
                     for (int e=0; e<rterm.length; e++) {
                        //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                        rterm[e] = leadingIsFirst ? (short)(rterm[e] - dvalues[e]) :
                                                    (short)(-rterm[e] - dvalues[e]);
                        if (rterm[e]!=0) {
                           lastVar = e;
                           divideNonZero = true;
                        }
                     }
                     // Swap order if necessary in revlex
                     if (divideNonZero && lastVar>=0) {
                        if (monomialOrdering.compare(reorder,rterm)==(leadingIsFirst ? -1 : 1)) {
                           leadingIsFirst = !leadingIsFirst;
                        }
                     }
                     if (isFinerLog) {
                        log.finer("rterm = "+arrayToString(rterm)+", leadingIsFirst="+leadingIsFirst);
                     }
                  }
               } while (divided && divideNonZero);
               //log.info("Finished dividing...");
               
               if (divideNonZero) {
                  
                  if (isFinerLog) {
                     log.finer("Remainder, dividing trailing monomial.");
                  }
                  
                  CompactBinomial divisor = null;
                  do {
                     Iterator divisors = initialTerms.compactBinomialDivisors(rterm,!leadingIsFirst);
                     if (divisors.hasNext()) {
                        Object o = divisors.next();
                        if (o instanceof List) {
                           divisor = (CompactBinomial)((List)o).get(0);
                        } else {
                           divisor = (CompactBinomial)o;
                        }
                        short [] dvalues = divisor.getValues();
                        if (isFinerLog) {
                           log.finer("divisor = "+arrayToString(dvalues));
                        }
                        divideNonZero = false;
                        for (int e=0; e<rterm.length; e++) {
                           //log.info("rterm["+leading+"]["+e+"] = "+rterm[leading][e]+" - "+ldvalues[e]+" + "+tdvalues[e]);
                           rterm[e] = leadingIsFirst ? (short)(rterm[e] + dvalues[e]) :
                                                       (short)(-rterm[e] + dvalues[e]);
                           if (rterm[e]!=0) {
                              divideNonZero = true;
                           }
                        }
                        if (monomialOrdering.compare(reorder,rterm)==(leadingIsFirst ? -1 : 1)) {
                           leadingIsFirst = !leadingIsFirst;
                        }
                        if (isFinerLog) {
                           log.finer("rterm = "+arrayToString(rterm)+", leadingIsFirst="+leadingIsFirst);
                        }
                     } else {
                        divisor = null;
                     }
                  } while (divisor!=null && divideNonZero);

                  if (divideNonZero) {
                     if (!leadingIsFirst) {
                        compactSwap(rterm);
                     }
                     if (isFinerLog) {
                        log.finer("Adding S-pair reduced: "+arrayToString(rterm));
                     }
                     CompactBinomial b = new CompactBinomial(rterm);
                     newAdds.add(b);
                     initialTerms.addBinomial(b,true);
                  }
               } else {
                  if (isFinerLog) {
                     log.finer("Reduces to zero, not added.");
                  }
               }
            }
            if (!duplicate) {
               if (isFinerLog) {
                  log.finer("adding basis element "+arrayToString(g.getValues()));
               }
               basis.add(g);
               //onlyBasisElements.addBinomial(g,true);
               added++;
            }
         }
         adds = newAdds;
      } while(adds.size()!=0);

      if (isFineLog) {
         log.fine("Basis size="+basis.size());
      }
      // Reduce the basis
      reduce(initialTerms);
      if (isFineLog) {
         log.fine("Finished, size="+basis.size());
      }
   }
    **/
   
   protected void reduce(BasisData abasis,BinomialTree initialTerms) {
      
      if (log.isLoggable(Level.FINE)) {
         log.fine("Reducing basis.");
      }
      initialTerms.groebnerReduce(true);
      abasis.length = 0;
      int leafCount = initialTerms.getRoot().leafCount;
      if (leafCount>abasis.data.length) {
         abasis.extend(leafCount-abasis.data.length);
      }
      MonomialTree.TreeIterator elements = initialTerms.iterator();
      while (elements.hasNext()) {
         if (abasis.length==abasis.data.length) {
            abasis.extend(128);
         }
         Object o = elements.next();
         if (o instanceof List) {
            for (Iterator toAdd = ((List)o).iterator();
                 toAdd.hasNext(); ) {
               abasis.data[abasis.length++] = (FullBinomial)toAdd.next();
               //checkNonZero(elements.current(),abasis.data[abasis.length-1]);
            }
         } else {
            abasis.data[abasis.length++] = (FullBinomial)o;
            //checkNonZero(elements.current(),abasis.data[abasis.length-1]);
         }
      }

   }
   
//   public void checkNonZero(MonomialTree.Entry [] current,FullBinomial b)
//   {
//      int lsum = 0;
//      int tsum = 0;
//      for (int i=0; i<b.leading.length; i++) {
//         lsum += b.leading[i];
//         tsum += b.trailing[i];
//      }
//      if (tsum==0 && lsum==0) {
//         StringBuffer sb = new StringBuffer();
//         for (int i=0; i<current.length; i++) {
//            sb.append(' ');
//            sb.append(Short.toString(current[i].value));
//         }
//         throw new RuntimeException("Zero binomial for "+sb.toString());
//      }
//   }
//
   public Iterator getElements() {
      return basis.iterator();
   }
   
   public BinomialIdeal getBasis() {
      return basis;
   }
   
   public void writeAsMatrix(Writer out,boolean compact)
      throws java.io.IOException
   {
      writeAsMatrix(out,compact,null);
   }
   public void writeAsMatrix(Writer out,boolean compact,int [] reorder)
      throws java.io.IOException
   {
      out.write(Integer.toString(basis.size()));
      out.write(' ');
      out.write(Integer.toString(order.size()));
      out.write('\n');
      Iterator elements = basis.iterator();
      while (elements.hasNext()) {
         Binomial b = (Binomial)elements.next();
         if (b instanceof CompactBinomial) {
            short [] values = ((CompactBinomial)b).getValues();

            if (compact) {
               for (int e=0; e<values.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  if (values[index]>=0) {
                     out.write(' ');
                  }
                  out.write(Short.toString(values[index]));
                  out.write(' ');
               }
            } else {
               for (int e=0; e<values.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  out.write(values[index]>0 ? Short.toString(values[index]) : "0");
                  out.write(' ');
               }
               for (int e=0; e<values.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  out.write(values[index]<0 ? Integer.toString(-values[index]) : "0");
                  out.write(' ');
               }
            }
         } else {
            short [] lvalues = b.getLeadingTerm();
            short [] tvalues = b.getTrailingTerm();

            if (compact) {
               for (int e=0; e<lvalues.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  int value = lvalues[index]-tvalues[index];
                  if (value>=0) {
                     out.write(' ');
                     out.write(Integer.toString(value));
                  } else {
                     out.write(Integer.toString(value));
                  }
                  out.write(' ');
               }
            } else {
               for (int e=0; e<lvalues.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  out.write(Short.toString(lvalues[index]));
                  out.write(' ');
               }
               for (int e=0; e<tvalues.length; e++) {
                  int index = reorder==null ? e : reorder[e];
                  out.write(Short.toString(tvalues[index]));
                  out.write(' ');
               }
            }
         }
         out.write('\n');
      }
      out.flush();
   }
   
   private String arrayToString(short [] values) {
      StringBuffer sb = new StringBuffer();
      for (int i=0; i<values.length; i++) {
         if (i!=0) {
            sb.append(' ');
         }
         sb.append(values[i]);
      }
      return sb.toString();
   }
   
   private String arrayToString(int [] values) {
      StringBuffer sb = new StringBuffer();
      for (int i=0; i<values.length; i++) {
         if (i!=0) {
            sb.append(' ');
         }
         sb.append(values[i]);
      }
      return sb.toString();
   }
   
}
